package org.xqh.study.leetcode.algorithm.twopointer;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName MinWindow
 * @Description 最小覆盖子串
 * https://leetcode-cn.com/problems/minimum-window-substring/
 * @Author xuqianghui
 * @Date 2021/2/9 15:28
 * @Version 1.0
 */
public class MinWindow {

    public static void main(String[] args) {
        String s = "cabwefgewcwaefgcf";
        String t = "cae";
        System.out.println(minWindow2(s, t));
    }

    public static void test(int[] abc){
        abc[0] = 0;
    }

    public static String minWindow(String s, String t) {
        char[] sc = s.toCharArray();
        char[] tc = t.toCharArray();
        if(sc.length < tc.length){
            return "";
        }
        int l = 0;
        int r = 0;
        int distance = 0;//标识 窗口内部 包含 了 T 中字符的个数.
        int[] winFreq = new int[128];//记录每个元素 出现的频数
        int[] tFreq = new int[128];
        for(char tt:tc){
            ++tFreq[tt];
        }
        int minLen = sc.length + 1;//
        int begin = 0;//记录开始位置

        while (r < sc.length){
            if(tFreq[sc[r]] == 0){
                r ++;
                continue;
            }
            if(tFreq[sc[r]] > winFreq[sc[r]]){
                distance ++;
            }
            ++winFreq[sc[r]];//频数 +
            r++;
            while (distance >= tc.length){
                if(r - l < minLen){
                    begin = l;
                    minLen = r -l;
                }

                if(tFreq[sc[l]] == 0){
                    l ++;
                    continue;
                }
                if(winFreq[sc[l]] == tFreq[sc[l]]){
                    distance --;
                }
                --winFreq[sc[l]];
                l++;
            }
        }
        if(minLen == sc.length + 1){//没有匹配到
            return "";
        }

        return s.substring(begin, minLen + begin);
    }

    public static String minWindow2(String s, String t){
        Map<Character,Integer> map = new HashMap<>();
        Map<Character,Integer> need = new HashMap<>();
        int b=1;
        for (char k:t.toCharArray()){
            need.put(k,b);
        }
        int left=0,right=0;
        int start = 0, len = Integer.MAX_VALUE;
        int valid = 0;
        while(right < s.length()){
            char c = s.charAt(right);
            right ++;
            if (need.containsKey(c)){
                map.put(c,map.getOrDefault(c,0)+1);
                if (map.get(c) == need.get(c)){
                    valid++;
                }
            }
            while(valid == need.size()){
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                char d = s.charAt(left);
                left++;
                if (need.containsKey(d)){
                    if (map.get(d) == need.get(d)){
                        valid--;
                    }
                    map.put(d,map.get(d)-1);
                }
            }
        }

        return len == Integer.MAX_VALUE ? "" : s.substring(start, len  + start);

    }

    /**
     * 判断 数组是否包含
     * @param freq  出现频数 数组
     * @param tc
     * @return
     */
    public static boolean contain(int[] freq, char[] tc){
        int[] copy = new int[freq.length];
        System.arraycopy(freq, 0, copy, 0, freq.length);
        boolean flag = true;
        for(char t:tc){
            if(copy[t] == 0){
                flag = false;
                break;
            }
            --copy[t];
        }
        return flag;
    }
}
